package sort.insert;

/**
 * 插入排序
 * 扑克牌 插入顺序
 * 假定 现在有的数组已经排好序。
 */
public class InsertSort {

    public void sort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int num = arr[i],j = i-1;//注意先要保存num（要插入的数字），防止移动位置把数字移不见了
            while (j>=0&&arr[j]>num){
                arr[j+1] = arr[j]; // 向 右推一步
                j--;
            }
            arr[j+1] = num;
        }
    }



    public void printArr(int[] arr){
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (int i = 0; i < arr.length; i++) {
            builder.append(arr[i]+",");
        }
        builder.append("]");
        System.out.println(builder.toString());
    }

    public static void main(String[] args) {
        int[] ints = {1, 4, 2, 0, 7, 8, 8, 11, 13};
        InsertSort insertSort = new InsertSort();
        insertSort.sort(ints);
        insertSort.printArr(ints);
    }

}
